1. Technical Field of the Invention
The present invention relates to computer-aided design (CAD) and, more particularly, to regularity extraction in the design of integrated circuits.
2. Background Art
In high-performance custom integrated circuit designs, designers take advantage of the high degree of regularity often present in circuits to generate efficient layouts in terms of area and performance as well as to reduce the design effort. Datapath circuits perform various arithmetic and multiplexing operations on wide buses. Such circuits have a very high degree of regularity. The design effort can be reduced by identifying or extracting regularity in circuits, thus improving the productivity of designers. Currently, however, datapath circuits in general-purpose microprocessors are designed almost entirely by hand. Existing CAD tools can not extract and utilize regularity to the extent necessary for competitive designs.
Various techniques for extraction of functional regularity have been proposed in the literature. For example, D. S. Rao et al., "On clustering for maximal regularity extraction," IEEE Tran. on CAD of Integrated Circuits and Systems, Vol. 12, No. 8 (August 1993), pp. 1198-1208, describes a string matching algorithm to find all instances of user-specified templates in the circuit, and then heuristically choose a subset of the set of templates to cover the circuit. The final cover is sensitive to the templates provided by the designer. M. R. Corazao et al., "Performance optimization using template mapping for datapath-intensive high-level synthesis," IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 15, No. 8 (August 1996), pp. 877-887, also assumes that a template library is provided, but claims to generate all complete as well as partial instances of a given template in the circuit. Another approach described in R.X.T. Nijssen et. al., "Regular layout generation of logically optimized datapaths," Proc. Int'l Symp. on Physical Design, (1997), pp. 42-47, involves choosing small logic components, such as latches, as templates, and then growing them to obtain bigger templates. This approach is highly dependent on the initial choice of templates.
The approaches in the above-listed articles either rely on the user specified templates or generate templates in an incomplete and ad hoc manner. Opportunities for regularity extraction are missed.
Accordingly, there is a need for techniques for systematic regularity extraction.